import java.util.Stack;

public class PalindromeList {
    public static boolean chkPalindrome(ListNode A) {
        if(A==null){
            return true;
        }
        ListNode fast=A,slow=A;
        while(fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        Stack<Integer> stack=new Stack<>();
        ListNode cur=A;
        ListNode dest=slow.next;
        if(fast.next==null){
            while(cur!=slow){
                stack.push(cur.val);
                cur=cur.next;
            }
            while(!stack.isEmpty()&&dest!=null){
                if(stack.pop()!=dest.val){
                    return false;
                }
                dest=dest.next;
            }
        }
        else{
            while(cur!=slow.next){
                stack.push(cur.val);
                cur=cur.next;

            }
            while(!stack.isEmpty()&&dest!=null){
                if(stack.pop()!=dest.val){
                    return false;
                }
                dest=dest.next;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        ListNode listNode1=new ListNode(1);
        ListNode listNode2=new ListNode(2);
        ListNode listNode3=new ListNode(2);
        ListNode listNode4=new ListNode(1);
        listNode3.next=listNode4;
        listNode2.next=listNode3;
        listNode1.next=listNode2;
        boolean a=chkPalindrome(listNode1);
        System.out.println(a);
    }
}